"""
双指针  利用两个指针去遍历数组 一般来说遍历数组采用的是单指针 index去遍历 ,两个指针一般是在有序数组中使用
一个放首,一个放尾,同时向中间遍历直到两个指针相交,完成遍历

用法  一般有两个指针 front tail 分别指向开始和结束位置
front = 0
tail = a.length()-1

一般循环结束条件采用的是 判断两个指针是否相遇
while(fron<tail)
循环结束条件一般就是其中一个指针遍历完成

使用范围
一般双指针在有序数组中使用的特别多 默认情况下,未排序数组也有应用
一般用于解决如下问题

1.两数求和
一般这种问题是问,寻找两个数的和为一个特定的值  这时候,如果数组有序,我们采用两个指针,分别从前和后往中间遍历,front移动和增大
tail移动和减小 通过特定的判断可以求出特定的和

2.in place交换
数组的in place(就地)交换一般得用双指针,不然数组中添加或删除一个元素,需要移动大量元素
这时候 一般是一个指针遍历,一个指针去找可以用来交换的元素


# 两数求和问题  : 给定一个整数数组，返回两个数字的索引，使它们相加之和等于一个特定的目标值。
# 你可以假设每个输入都恰好有一个解决方案。
# Given nums = [2, 7, 11, 15], target = 9,
# Because nums[0] + nums[1] = 2 + 7 = 9,
# return [0, 1].

# 思路 : 使用 hashmap hashmap是内部存储方式为哈希表的map结构,哈希表可以达到查找o(1)
# 遍历数组中的每个元素 nums[i]。
# 每次遍历时，计算目标值与当前值的差值：complement = target - nums[i]。
# 检查这个 complement 是否已经在哈希表中：
# 如果在，说明找到了一对解，返回 [hashmap[complement], i]。
# 如果不在，将当前值及其索引存入哈希表中。
# 该方法只需遍历一次数组，并且查找操作的时间复杂度为 O(1)。


class Solution:
    def two_sum(self, nums, target):
        hashmap = {}  # 存储数值和对应的索引
        for i, num in enumerate(nums):
            complement = target - num  # 计算需要的补数
            if complement in hashmap:
                return [hashmap[complement], i]  # 找到解，返回两个索引
            hashmap[num] = i  # 将当前数值和索引存入哈希表
        return []  # 没有找到解时返回空列表

# 思路 : 1,双重循环  没啥含量就是速度很慢

class Solution:
    def two_sum(self, nums, target):
        # 遍历数组中的每一个元素
        for i in range(len(nums)):
            # 从当前元素之后的元素中寻找配对
            for j in range(i + 1, len(nums)):
                # 检查两数之和是否等于目标值
                if nums[i] + nums[j] == target:
                    return [i, j]
        # 如果没有找到符合条件的两个数，可以返回空列表或其他提示信息
        return []


# 思路 : 2,排序  通过排序,然后用两个指针从前后扫描逼近真值,因为一定会有一个值满足,然后通过原数组里找到对应的下标
class Solution:
    def two_sum(self, nums, target):
        # 创建一个列表，每个元素是 (数值, 原始索引)，用于排序后仍能获取原始索引
        indexed_nums = [(num, i) for i, num in enumerate(nums)]
        # 按照数值进行排序，便于使用双指针法查找
        indexed_nums.sort()

        # 初始化两个指针，left 从前往后，right 从后往前
        left = 0
        right = len(indexed_nums) - 1

        # 当两个指针未相遇时，持续查找
        while left < right:
            # 计算当前两个指针所指数值的和
            current_sum = indexed_nums[left][0] + indexed_nums[right][0]

            # 如果找到和等于目标值的两个数，返回它们在原数组中的索引
            if current_sum == target:
                return [indexed_nums[left][1], indexed_nums[right][1]]

            # 如果当前和小于目标值，说明需要更大的数，将左指针右移
            elif current_sum < target:
                left += 1

            # 如果当前和大于目标值，说明需要更小的数，将右指针左移
            else:
                right -= 1

        # 如果没有找到符合条件的两个数，返回空列表
        return []
三数组求和
问题 :  给定一个包含 n 个整数的数组 S，数组 S 中是否存在元素 a、b、c，使得 a + b + c = 0？找出数组中所有和为零的唯一三元组。
三元组 (a, b, c) 中的元素必须按非降序排列。（即 a ≤ b ≤ c）解集不能包含重复的三元组。 例如，给定数组 S = {-1 0 1 2 -1 -4}，

思路 如果我们随机确定了一个数a 然后在剩下的数里面找到2个数和为0-a 就和2数求和问题一样
难点
数组里允许重复的数
结果要按升序排序
结果中不能出现重复的结果

可以选择3个变量 left mid right 在循环的时候 永远保证相对顺序就行了 在插入结果的时候就自然是升序的

解题思路
首先我们考虑如何确定第一个数left,这肯定是我们第一层循环 ,第一个数可不能无限制的随便选 ,因为要保证上面的几个条件都满足,
要保证它时刻是最小的数,那么可以考虑left取到全部非正数就可行 如果要和为0,至少要有一个非正数
for(int left =0; left< nums.length && nums[left] <=0;left++)

然后就是mid和right的确定了,mid和right分别从两端往中间扫描 如果mid+right 还比较小,就需要mid右移 反之right左移

class Solution:

解决方案类，提供方法来寻找一个数组中所有不重复的三元组，这些三元组的和为零。

def three_sum(self, s):

寻找所有不重复的三元组，这些三元组的和为零。

参数:
s: 一个整数列表。

返回:
一个二维列表，包含所有不重复的三元组。

# 对数组进行排序，以便后续使用双指针技术
s.sort()
# 初始化结果列表
res = []

# 遍历数组，寻找所有可能的三元组
for i in range(len(s)):
    # 跳过重复的元素，以避免重复的三元组出现
    if i > 0 and s[i] == s[i-1]:
        continue

    # 初始化目标值，即当前元素的相反数
    target = -s[i]
    # 初始化双指针，左指针从当前元素的下一个开始，右指针从数组的末尾开始
    left,right = i+1,len(s)-1

    # 当左指针小于右指针时，执行循环
    while left < right:
        # 计算当前左指针和右指针指向元素的和
        current_sum = s[left] + s[right]

        # 如果当前和等于目标值，说明找到了一个有效的三元组
        if current_sum == target:
            # 将这个三元组添加到结果列表中
            res.append([s[i],s[left],s[right]])

            # 移动左指针，跳过所有重复的元素
            while left < right and s[left] == s[left+1]:
                left += 1

            # 移动右指针，跳过所有重复的元素
            while left < right and s[right] == s[right-1]:
                right -= 1

            # 同时移动左右指针，继续寻找下一组可能的三元组
            left += 1
            right -= 1
        # 如果当前和小于目标值，移动左指针以增加和的值
        elif current_sum < target:
            left += 1
        # 如果当前和大于目标值，移动右指针以减少和的值
        else:
            right -= 1

# 返回所有找到的不重复三元组
return res


三数组问题变种

给定一个包含 n 个整数的数组 S，在 S 中找出三个整数，使得它们的和最接近给定的数 target 。返回这三个整数的和。你可以假设每个输入都只有一个正确答案。
✅ 解题思路：
排序数组：对数组进行排序，便于后续双指针查找和去重。
固定第一个数 nums[i]：
遍历数组，每次固定一个数作为三元组的第一个元素。
使用双指针在剩余数组中查找两个数之和：
设置 left = i + 1 和 right = len(nums) - 1。
计算当前三数之和 current_sum = nums[i] + nums[left] + nums[right]。
比较 current_sum 与 target 的差距：
如果等于 target，直接返回结果。
如果更接近 target，则更新最近的和。
根据大小关系移动指针（left 右移或 right 左移）。
避免重复计算（可选优化）：
跳过相同的第一个数，减少无效遍历。




class Solution:

    解决三数之和最接近目标值的问题。

    方法:
        three_sum_closest: 接受一个整数数组和一个目标值，返回三个整数的和，使得这个和最接近目标值。


    def three_sum_closest(self, nums, target):

        寻找数组中三个数的和，使得这个和最接近目标值。

        参数:
            nums: 整数数组。
            target: 目标值。

        返回:
            最接近目标值的三个数的和。

        # 对数组进行排序，以便后续使用双指针技术
        nums.sort()
        # 初始化最接近目标值的和为无穷大，以便后续比较
        closest_sum = float('inf')
        # 遍历数组，固定一个数，寻找其他两个数
        for i in range(len(nums)):
            # 跳过重复的数，避免重复计算
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 使用双指针技术，一个从左开始，一个从右开始
            left, right = i + 1, len(nums) - 1
            # 当左指针小于右指针时，执行循环
            while left < right:
                # 计算当前三个数的和
                current_sum = nums[i] + nums[left] + nums[right]
                # 如果当前和更接近目标值，更新最接近的和
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
                # 根据当前和与目标值的比较，移动指针
                if current_sum == target:
                    # 如果当前和等于目标值，直接返回结果
                    return current_sum
                elif current_sum < target:
                    # 如果当前和小于目标值，左指针右移
                    left += 1
                else:
                    # 如果当前和大于目标值，右指针左移
                    right -= 1
        # 返回最接近目标值的和
        return closest_sum

两指针解决装水问题

问题 : 给定 n 个非负整数 a1、a2、…、an，其中每个数代表坐标 (i, ai) 处的一个点。画 n 条垂直线，使得第 i 条线的两个端点分别为 (i, ai) 和 (i, 0) 。找出两条线，它们与 x 轴构成一个容器，使得该容器能容纳最多的水。
注意：容器不能倾斜。


思路 首先要明确一个我之前一直理解错的，它的题目是随意找2个木板构成木桶，容量最大，我之前以为是所有的木板已经在它的位置上了，然后找其中容量最大的——你加的水是可以漫过中间比较短的板子的。

如果按题意来，就简单了。

我们用两个指针来限定一个水桶，left,right。
h[i]表示i木板高度。
Vol_max表示木桶容量最大值

由于桶的容量由最短的那个木板决定：
Vol = min(h[left],h[right]) * (right - left)

left和right分别指向两端的木板。
left和right都向中央移动，每次移动left和Right中间高度较小的（因为反正都是移动一次，宽度肯定缩小1，这时候只能指望高度增加来增加容量，肯定是替换掉高度较小的，才有可能找到更大的容量。）
看新桶子的容量是不是大于Vol_max，直到left和right相交。

✅ 解题思路：
初始化两个指针：
left 指向数组开头（最左的线）
right 指向数组末尾（最右的线）
计算当前容器的容量：
容量 = min(height[left], height[right]) * (right - left)
即：两线中较短的一条决定了高度，两条线之间的距离是宽度
移动较短的那条指针：
因为想尝试找到更高的线来增加容量
如果移动较高的那条线，宽度减少且高度不会变大，容量也不可能更大
持续更新最大容量，直到两个指针相遇

class Solution:
    '''
    本类用于解决容器最大水量问题。

    问题描述：给定一个高度数组，找出两个索引之间的最大容器面积。
    解决方案：使用双指针技术，从数组的两端开始，向中间移动，以找到最大面积。
    '''

    def max_area(self, height):
        '''
        计算给定高度数组的最大容器面积。

        参数:
        height (List[int]): 一个整数列表，表示各个高度。

        返回:
        int: 最大容器的面积。
        '''
        # 初始化左右指针和最大面积变量
        left = 0
        right = len(height) - 1
        max_area  = 0

        # 当左指针小于右指针时，执行循环
        while left < right:
            # 计算当前容器的面积，取左右高度的最小值乘以宽度
            current_area = min(height[left], height[right]) * (right - left)
            # 更新最大面积
            max_area = max(max_area, current_area)

            # 移动指针，如果左高度小于右高度，则左指针右移，否则右指针左移
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        # 返回计算出的最大面积
        return max_area


删除有序数组重复元素
问题 给定一个已排序的数组，在原地删除重复项，使得每个元素只出现一次，并返回新的长度。
不要为另一个数组分配额外的空间，你必须在原地使用常量内存完成此操作。
例如，给定输入数组 nums = [1, 1, 2]，你的函数应该返回长度 = 2，且 nums 的前两个元素分别为 1 和 2。在新长度之后留下什么内容无关紧要。

这题因为是排序好的，所以很容易做。这里关键点是”删除多余元素”这句话，这里其实不是真的删除，因为题目要求不能用额外的空间，所以最好的思路是替换。题目也说了“It doesn’t matter what you leave beyond the new length.”，所以我们只要把后面的元素放到前面来就行了。

这里用2个指针:

1个指针i从1移动到length
1个指针newlen记录不重复的个数，只有出现不重复的时候它才能+1


✅ 解题思路：
初始化两个指针：
i：指向当前不重复部分的最后一个位置（初始为 0）
j：遍历数组的指针（从 1 开始）
遍历数组：
如果 nums[j] != nums[i]，说明遇到了一个新值。
将 nums[++i] = nums[j]，把新值放到 i + 1 的位置。
最终返回：
返回 i + 1 表示去重后的数组长度。
原数组的前 i + 1 个元素就是不含重复项的结果。


删除重复元素
给定一个数组和一个值，就地移除该值的所有实例，并返回新的长度。
不要为另一个数组分配额外的空间，你必须在原地使用常量内存完成此操作。
元素的顺序可以改变。在新长度之后留下什么并不重要。

nums = [3,2,2,3] val=3

✅ 解题思路：
初始化两个指针：
i：指向当前可以放置非目标值的位置（从 0 开始）
j：遍历数组的指针（从 0 到 len(nums)-1）
遍历数组：
如果 nums[j] != val，说明这个值不是要删除的值。
将其交换或赋值给 nums[i]，然后 i += 1。
最终返回：
返回 i，即为移除目标值后的新长度。
注意：我们不真正“删除”元素，而是把不需要删除的元素移到前面，后面的元素可以忽略。
"""


class Solution:

    def remove_duplicates(self, nums):
        """
        在原地删除有序数组中的重复项，并返回新的长度。

        参数:
            nums: List[int] - 一个已排序的整数数组

        返回:
            int - 不含重复项的数组长度
        """
        if not nums:
            return 0

        i = 0  # 指向不重复部分的最后一个位置

        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]

        return i + 1

    def remove_element(self, nums, val):
        """
        在原地移除数组中所有等于 val 的元素，并返回新的长度。

        参数:
            nums: List[int] - 输入数组
            val: int - 要移除的值

        返回:
            int - 移除后的数组长度
        """
        i =0

        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1

        return i



if __name__ == '__main__':
    nums = [1, 1, 2, 2, 3, 4, 4, 5]
    length = Solution.remove_duplicates(nums)
    print("新长度:", length)  # 输出: 新长度: 5
    print("去重后数组:", nums[:length])  # 输出: 去重后数组: [1, 2, 3, 4, 5]
    solution = Solution()
    nums = [3, 2, 2, 3]
    val = 3
    length = solution.remove_element(nums, val)
